package quickSort;

import java.util.Arrays;

public class Solution {
    public static void main(String[] args) {
        int[] arr = new int[]{10,9,8,7,66,-9999,55,4,10,22,18,0,-7,10008,8};
        quickSort(arr);
        System.out.println(Arrays.toString(arr));
    }
    private static void quickSort(int[] nums){
        quick_sort(nums,0,nums.length-1);
    }
    private static void quick_sort(int[] nums,int l,int r){
        if(l<r){
            int pivot = partition(l,r,nums);
            quick_sort(nums,l,pivot-1);
            quick_sort(nums,pivot+1,r);
        }
    }
    // 获取下次分割的位置
    private static int partition(int left,int right,int[] nums){
        int pivot = nums[right];
        int l = left;
        int r = right;
        while (l<r){
            // 因为选择的是右边为pivot 所以要先在左边挖空
            while (l<r&&nums[l]<=pivot){
                l++;
            }
            nums[r] = nums[l];
            while (l<r&&nums[r]>=pivot){
                r--;
            }
            nums[l] = nums[r];
        }
        nums[r] = pivot;
        return r;
    }
}
